package 搜索算法;


import jdk.nashorn.internal.objects.Global;

import java.util.ArrayList;
import java.util.Stack;

@SuppressWarnings("all")
public class DFS {
    static Stack<Character> res = new Stack<>();
    public static void main(String[] args) {
        String s = "19216801";
        Stack<String> res = new Stack<>();
        int index = -1;
        ipaddress(s,res,index);
    }

    /**
     * 进一步的参数优化，此时我们只需要待排序的字符数组
     * 最终我们将dfs函数的参数优化到只需要待排序的数组即可，其他多余的参数都可以被省略
     * @param p
     */
    public static void dfs(char[] p) {
        if (res.size() == p.length) {
            for (Character re : res) {
                System.out.print(re+" ");
            }
            System.out.println(); // 换行
            return;
        }
        for (int i = 0; i < p.length; i++) {
            char temp = p[i];
            if (temp != ' ') {
                res.add(temp);
                p[i] = ' ';
                dfs(p);
                res.pop();
                p[i] = temp;
            }
        }
    }
    /**
     * 优化了参数，可以将结果集作为一个静态成员变量即可，无需作为参数
     * @param p
     * @param b
     */
    public static void dfs(char[] p,int[] b) {
        if (res.size() == p.length) {
            for (Character re : res) {
                System.out.print(re+" ");
            }
            System.out.println(); // 换行
            return;
        }
        for (int i = 0; i < p.length; i++) {
            if (b[i] == 0) {
                res.add(p[i]);
                b[i] = 1;
                dfs(p,b);
                b[i] = 0;
                res.pop();
            }
        }
    }

    /**
     * dfs求解字符的全排列问题
     * 具体的例子辅助思考：
     *  假设当前的字符数组为  {'A','B','C'},下面我们模拟dfs算法的过程手写一遍
     *  假设 res = [] 为存放一种结果数组   b = [0,0,0] 表示是否选取该元素的数组 如果选择第i个元素，
     *  我们将第i个元素的b[i]修改为1
     *  我们考虑一下每一轮选择的边界条件是什么? 显然如果我们找到了一种选择，此时res的长度应该为3，所以我们直接比较res
     *  和数组的长度即可，如果选择直接输出当前选择
     *  先分析dfs函数的参数：
     *      首先这个问题实际上可以转化为树状图形，初始时我们可以选择的元素有三种分别为A,B,C
     *      假设当前我们选择的为A，将A作为树的root节点
     *                          A
     *                        B   C
     *                      C       B
     *      所以我们需要知道当前一层选择的上一层的选择，所以我们需要传入一个标记数组 b,b[i]表示第i个元素是否被选择
     *      如果选择我们将其修改为1，此外我们还需要一个容器来存储我们每一轮选择的结果，退出当前递归的条件为结果集合
     *      的长度为数组长度
     * @param p
     * @param index
     */
    public static void dfs(char[] p, Stack<Character> res, int[] b) {
        if (res.size() == p.length) { // 边界条件
            // 输出res中的结果即可
            for (Character re : res) {
                System.out.print(re+" ");
            }
            System.out.println(""); // 换行
            return;
        }
        // dfs的部分
        for (int i = 0; i < p.length; i++) {
            char temp = p[i];
            // 判断当前元素是否可以被选中
            if (b[i] == 0) { // 说明当前元素没有被选中
                b[i] = 1; // 修改
                res.add(temp); // 添加进当前的结果集合
                dfs(p, res, b); // 进入到下一层
                b[i] = 0; // 还原
                res.pop(); // 直接移除当前添加进入的元素
            }
        }
    }

    /**
     * 划分字符串为正确的ip地址
     *
     * 异常：????????  淦!!!  为什么????????
     */
    public static void ipaddress(String s,Stack<String> res,int index) {
        // 判断边界
        if (res.size() == 4 || index == s.length() - 1) {
            if (res.size() == 4 && index == s.length() - 1) {
                StringBuilder ip = new StringBuilder();
                for (int i = 0; i < res.size(); i++) {
                    if (i != res.size() - 1) {
                        ip.append(res.get(i)+".");
                    } else {
                        ip.append(res.get(i));
                    }
                }
                System.out.println(ip.toString());
            }
            return;
        }
        for (int i = 0; i < 4; i++) {
            String substring = s.substring(index + 1, i);
            System.out.println(substring);
            if (Integer.parseInt(substring) < 256 && (substring == "0" || !substring.startsWith("0"))) {
                res.add(substring);
                ipaddress(s,res,index+i);
                res.pop();
            }
        }
    }
}
